﻿using System.Collections.Generic;

namespace TC.Vacation.Spider.Core.Hash
{
    /// <summary>
    /// 一致性hash环，平均分发抓取url到各个slave上，实现负载均衡
    /// </summary>
    internal class KetamaNodeLocator
    {
        private SortedList<long, string> ketamaNodes = new SortedList<long, string>();
        private int numReps = 160;

        public KetamaNodeLocator(List<string> nodes, int nodeCopies)
        {
            ketamaNodes = new SortedList<long, string>();

            numReps = nodeCopies;
            //对所有节点，生成nCopies个虚拟结点
            foreach (string node in nodes)
            {
                //每四个虚拟结点为一组
                for (int i = 0; i < numReps / 4; i++)
                {
                    //GetNodeForKey方法为这组虚拟结点得到惟一名称 
                    byte[] digest = HashAlgorithm.ComputeMd5(node + i);
                    //Md5是一个16字节长度的数组，将16字节的数组每四个字节一组，分别对应一个虚拟结点
                    for (int h = 0; h < 4; h++)
                    {
                        long m = HashAlgorithm.Hash(digest, h);
                        ketamaNodes[m] = node;
                    }
                }
            }
        }

        private string GetPrimary(string k)
        {
            byte[] digest = HashAlgorithm.ComputeMd5(k);
            string rv = GetNodeForKey(HashAlgorithm.Hash(digest, 0));
            return rv;
        }

        /// <summary>
        /// 二分法查找节点
        /// </summary>
        /// <param name="hash">The hash.</param>
        /// <returns></returns>
        private string GetNodeForKey(long hash)
        {
            string rv;
            long key = hash;
            int pos = 0;
            if (!ketamaNodes.ContainsKey(key))
            {
                int low, high, mid;
                low = 1;
                high = ketamaNodes.Count - 1;
                while (low <= high)
                {
                    mid = (low + high) / 2;
                    if (key < ketamaNodes.Keys[mid])
                    {
                        high = mid - 1;
                        pos = high;
                    }
                    else if (key > ketamaNodes.Keys[mid])
                        low = mid + 1;
                }
            }

            rv = ketamaNodes.Values[pos + 1].ToString();
            return rv;
        }
    }
}
